'''
给定一个二叉树，返回它的 后序 遍历。

示例:

输入: [1,null,2,3]  
   1
    \
     2
    /
   3 

输出: [3,2,1]

'''
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        result = []
        def postra(root):
            if root == None:
                return
            else:
                postra(root.left)
                postra(root.right)
                result.append(root.val)
        postra(root)
        return result
#迭代
class Solution:
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        result = []
        stack = []
        if root == None:
            return result
        stack.append(root)
        while len(stack) > 0:
            tmp = stack[-1]
            if tmp.right == None and tmp.left == None:
                result.append(stack.pop().val)
            else:
                if tmp.right != None:
                    stack.append(tmp.right)
                    tmp.right = None
                if tmp.left != None:
                    stack.append(tmp.left)
                    tmp.left = None
        return result